/*
 * mm.c - 实现一个动态内存分配器，包括 malloc、free 和 realloc 函数。
 * 
 * ### 堆块结构 ###
 * 每个堆块由以下几个部分组成：
 * 1. 块头（Header）：包含块大小和分配标志， 4字节。
 * 2. 有效负载（Payload）：存储用户数据和前后空闲块地址，最小8字节。
 * 3. 块尾（Footer）：包含块大小和分配标志， 4字节。
 * 4. 空闲块最小大小为16字节。有效负载中，前8个字为前驱空闲块与后驱空闲块，用于支持双向合并。
 
 * ### 核心操作 ###
 * - **分配 (malloc)**：在空闲链表中找到一个适配的块，分割后分配给用户。
 * - **释放 (free)**：标记块为空闲并尝试与相邻块合并。
 * - **重分配 (realloc)**：为用户分配新的块，复制数据，并释放旧块。
 * - **空闲链表操作**：
 *   - 插入(insert)：将新释放或合并后的空闲块按大小升序插入链表。
 *   - 删除(delete)：分配或合并块时从链表中移除对应节点。
 *

 * ### 堆检查器 ###
 * mm_check 函数扫描堆的块，并检查以下一致性条件：
 * - 堆结构和指针的有效性。
 * - 空闲链表的正确性。
 * - 无未合并的连续空闲块。
 */

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>

#include "mm.h"
#include "memlib.h"

/*********************************************************
 * NOTE TO STUDENTS: Before you do anything else, please
 * provide your team information in the following struct.
 ********************************************************/
team_t team = {
    /* Team name */
    "TJU",
    /* First member's full name */
    "杨思祺",
    /* First member's email address */
    "3023205027@tju.edu.cn",
    /* Second member's full name (leave blank if none) */
    "",
    /* Second member's email address (leave blank if none) */
    ""
};

/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8

/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)


#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))

#define WSIZE 4
#define DSIZE 8
#define CHUNKSIZE (1 << 12)   // 扩展堆的默认大小

#define PACK(size, alloc) ((size) | (alloc))
#define GET(addr) (*(unsigned int*)(addr))  
#define PUT(addr, val) (*(unsigned int*)(addr) = (val))  

/* 获取块的大小和分配状态 */
#define GET_SIZE(addr) (GET(addr) & ~0x7)  
#define GET_ALLOC(addr) (GET(addr) & 0x1)  

/* 计算块头和块尾指针 */
#define HDRP(addr) ((char*)(addr) - WSIZE)
#define FTRP(addr) ((char*)(addr) + GET_SIZE(HDRP(addr)) - DSIZE)

/* 计算前后块的指针 */
#define NEXT_BLKP(addr) ((char*)(addr) + GET_SIZE(((char*)(addr) - WSIZE)))  
#define PREV_BLKP(addr) ((char*)(addr) - GET_SIZE(((char*)(addr) - DSIZE)))  

/* 空闲链表指针操作 */
#define NEXT_FREE(addr) (*(int *)((char*)(addr)))
#define PREV_FREE(addr) (*(int *)((char*)(addr) + 4))
#define PUT_FREE(addr, val) ((addr) = (val))

static char* heap_listp;  // 指向堆的起始位置
static char* free_head;   // 空闲链表的头指针

/*
 * mm_check - 检查堆的一致性。
 *
 * 功能：
 * - 遍历堆块，验证块大小、分配状态、指针合法性。
 * - 遍历空闲链表，验证链表的完整性和一致性。
 *
 * 返回值：
 * - 1：检查通过。
 * - 0：检查失败，并输出错误信息。
 *
 * 实现：
 * 1. 遍历堆，检测是否存在非法指针、未合并的空闲块。
 * 2. 遍历空闲链表，检测是否包含分配块或无效指针。
 */


int mm_check(void) {
    char *bp = heap_listp;

    // 1. 遍历整个堆，检查空闲块和已分配块的基本一致性
    while (GET_SIZE(HDRP(bp)) > 0) {
        // 检查堆块是否指向有效地址
        if ((void *)bp < (void *)mem_heap_lo() || (void *)bp > (void *)mem_heap_hi()) {
            printf("Error: Block pointer out of bounds.\n");
            return 0;
        }

        // 检查块的分配标志和大小是否合理
        if (GET_SIZE(HDRP(bp)) % ALIGNMENT != 0) {
            printf("Error: Block size is not aligned.\n");
            return 0;
        }

        // 检查相邻空闲块是否已合并
        if (!GET_ALLOC(HDRP(bp)) && !GET_ALLOC(HDRP(NEXT_BLKP(bp)))) {
            printf("Error: Two consecutive free blocks found.\n");
            return 0;
        }

        bp = NEXT_BLKP(bp);
    }

    // 2. 遍历空闲链表，检查链表一致性
    char *free_bp = NEXT_FREE(free_head);
    while (free_bp != NULL) {
        // 检查空闲块是否标记为free
        if (GET_ALLOC(HDRP(free_bp))) {
            printf("Error: Allocated block found in free list.\n");
            return 0;
        }

        // 检查空闲链表中的指针是否指向有效块
        if ((void *)free_bp < (void *)mem_heap_lo() || (void *)free_bp > (void *)mem_heap_hi()) {
            printf("Error: Free list pointer out of bounds.\n");
            return 0;
        }

        free_bp = NEXT_FREE(free_bp);
    }

    printf("Heap consistency check passed.\n");
    return 1; 
}

/*
 * insert - 将空闲块插入空闲链表。
 *
 * 功能：
 * - 按块大小升序将空闲块插入链表。
 *
 * 实现：
 * 1. 遍历空闲链表，找到插入位置。
 * 2. 更新新块的前后指针。
 * 3. 维护链表的完整性。
 */


void insert(char* bp) {

    // 如果链表为空，将当前块插入为第一个空闲块
    if(NEXT_FREE(free_head) == NULL) {
        PUT_FREE(NEXT_FREE(free_head), bp);
        PUT_FREE(PREV_FREE(bp), free_head);
        PUT_FREE(NEXT_FREE(bp), NULL);
    }
    else {
        // 遍历链表，找到合适的插入位置
        char* cur_free = NEXT_FREE(free_head);
        while(GET_SIZE(HDRP(cur_free)) < GET_SIZE(HDRP(bp)) && NEXT_FREE(cur_free) != 0) cur_free = NEXT_FREE(cur_free);
        if(cur_free == NEXT_FREE(free_head)) {
            // 插入到链表头部
            PUT_FREE(NEXT_FREE(bp), cur_free);
            PUT_FREE(PREV_FREE(cur_free), bp);
            PUT_FREE(PREV_FREE(bp), free_head);
            PUT_FREE(NEXT_FREE(free_head), bp);
        }
        else {
            // 插入到链表中间或尾部
            PUT_FREE(NEXT_FREE(bp),cur_free);
            PUT_FREE(PREV_FREE(bp), PREV_FREE(cur_free));
            PUT_FREE(NEXT_FREE(PREV_FREE(cur_free)), bp);
            PUT_FREE(PREV_FREE(cur_free), bp);
        }
    }
}

/*
 * delete - 从空闲链表中删除一个块。
 *
 * 功能：
 * - 从链表中移除指定块，更新链表指针。
 *
 * 实现：
 * 1. 根据被删除块的位置调整链表指针。
 * 2. 如果是头或尾节点，需要特殊处理。
 */


void delete(char* bp) {
    if(NEXT_FREE(free_head)== bp && NEXT_FREE(bp) == NULL) {
        // 如果链表中只有一个块
        PUT_FREE(NEXT_FREE(free_head), NULL);
    }
    else if(NEXT_FREE(free_head)== bp) {
        // 如果删除的是链表头部块
        PUT_FREE(NEXT_FREE(free_head), NEXT_FREE(NEXT_FREE(free_head)));
        PUT_FREE(PREV_FREE(NEXT_FREE(bp)), free_head);
    }
    else if(NEXT_FREE(bp) == NULL) {
        // 如果删除的是链表尾部块
        PUT_FREE(NEXT_FREE(PREV_FREE(bp)), NULL);
    }
    else {
        // 删除链表中间块
        char* prev = PREV_FREE(bp);
        PUT_FREE(NEXT_FREE(prev), NEXT_FREE(bp));
        PUT_FREE(PREV_FREE(NEXT_FREE(bp)), prev);
    }
}

/*
 * coalesce - 合并相邻的空闲块。
 *
 * 功能：
 * - 如果当前块的前后块为空闲，合并这些块。
 *
 * 实现：
 * 1. 检查前后块的分配状态。
 * 2. 合并块后更新大小和指针。
 * 3. 将合并后的块插入空闲链表。
 */


void* coalesce(void* bp) {
    size_t size = GET_SIZE(HDRP(bp));
    size_t prev = GET_ALLOC(HDRP(PREV_BLKP(bp)));
    size_t next = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
    if(prev && next) {
        // 前后块均已分配，无需合并
        insert(bp);
        return bp;
    }
    else if(prev && !next) {
        // 合并当前块和后面的空闲块
        delete(NEXT_BLKP(bp));
        int merge_size = size + GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(merge_size, 0));
        PUT(HDRP(bp), PACK(merge_size, 0));
    }
    else if(!prev && next) {
        // 合并当前块和前面的空闲块
        delete(PREV_BLKP(bp));
        int merge_size = size + GET_SIZE(HDRP(PREV_BLKP(bp)));
        PUT(HDRP(PREV_BLKP(bp)), PACK(merge_size, 0));
        PUT(FTRP(PREV_BLKP(bp)), PACK(merge_size, 0));
        bp = PREV_BLKP(bp);
    }
    else if(!prev && !next) {
        // 合并当前块、前块和后块
        delete(PREV_BLKP(bp));
        delete(NEXT_BLKP(bp));
        int merge_size = size + GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(PREV_BLKP(bp)), PACK(merge_size, 0));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(merge_size, 0));
        bp = PREV_BLKP(bp);
    }
    else return (void*)-1;
    // 将合并后的块插入空闲链表
    insert(bp);
    return bp;
}

/*
 * extend_heap - 扩展堆空间并尝试与相邻块合并。
 *
 * 功能：通过增加堆空间创建一个新的空闲块，并尝试与前后的空闲块合并。
 * 参数：words - 需要扩展的字数（按字对齐）。
 * 返回值：返回指向新空闲块的指针，失败时返回 NULL。
 */

static void *extend_heap(size_t words) 
{   // 如果请求的字数是奇数，将其调整为偶数，确保块的对齐性
    if(words % 2) words++;
    // 计算需要扩展的字节数
    size_t size = words * WSIZE;
    char* bp;
    if((long)(bp = mem_sbrk(size)) == -1) {
        return (void*)NULL;
    }
    // 设置新分配块的头部和脚部，标记为未分配
    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));
    // 尝试将新分配的块与相邻空闲块合并
    return coalesce(bp);
}

/*
 * find_fit - 在空闲链表中查找适配的空闲块。
 *
 * 功能：遍历空闲链表，找到满足请求大小的第一个空闲块。
 * 参数：asize - 调整后需要分配的块大小。
 * 返回值：返回指向合适块的指针；若找不到合适块，返回 NULL。
 */

inline void *find_fit(size_t asize) {
    char* tmp = free_head;
    while(tmp != NULL) {
        if(GET_SIZE(HDRP(tmp)) >= asize) return tmp;
        else tmp = NEXT_FREE(tmp);
    }
    return (void*)NULL;
}

/*
 * place - 将请求大小的块放置到空闲块中，并处理剩余空间。
 *
 * 功能：将请求大小的块分配给空闲块。如果剩余空间足够大，则分裂空闲块；
 *       否则将整个空闲块分配。
 * 参数：bp - 指向空闲块的指针。
 *      asize - 调整后的块大小。
 */

inline void place(void *bp, size_t asize) {
    int reminder = (int)GET_SIZE(HDRP(bp)) - (int)asize;
    if(reminder >= 4 * WSIZE) {
        // 若剩余空间足够大，则分裂空闲块
        char *remind_bp = (char*)(HDRP(bp) + asize);
        // 初始化剩余块的头部和脚部
        PUT(remind_bp, PACK((size_t)reminder, 0));
        remind_bp += WSIZE;
        PUT(FTRP(remind_bp), PACK((size_t)reminder, 0));
        // 将剩余块插入空闲链表
        insert(remind_bp);
        // 更新当前块的头部和脚部为已分配
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1));
    }
    // 若剩余空间不足，直接分配整个块
    else {
        PUT(HDRP(bp), PACK(GET_SIZE(HDRP(bp)), 1));
        PUT(FTRP(bp), PACK(GET_SIZE(HDRP(bp)), 1));
    }
    // 从空闲链表中移除已分配的块
    delete(bp);
}

/*
 * mm_init - 初始化内存分配器。
 *
 * 功能：
 * - 创建一个空堆，并初始化空闲链表。
 *
 * 实现：
 * 1. 分配初始堆空间，设置序言和结尾块。
 * 2. 扩展堆以创建初始空闲块。
 * 3. 初始化空闲链表头。
 */


int mm_init(void)
{
    // 请求初始堆空间
    if((long)(heap_listp = mem_sbrk(6 * WSIZE)) == -1) {
        return -1;
    }
    // 初始化堆的初始块结构
    PUT(heap_listp, 0);                             // 对齐填充
    PUT(heap_listp + 1 * WSIZE, 0);                 // 对齐填充
    PUT(heap_listp + 2 * WSIZE, PACK(0, 1));        // 空闲链表头指针
    PUT(heap_listp + 3 * WSIZE, PACK(DSIZE, 1));    // 序言块头部
    PUT(heap_listp + 4 * WSIZE, PACK(DSIZE, 1));    // 序言块尾部
    PUT(heap_listp + 5 * WSIZE, PACK(0, 1));        // 终止块头部
    // 初始化空闲链表头
    free_head = heap_listp + 2 * WSIZE;
    PUT_FREE(NEXT_FREE(free_head), NULL);
    heap_listp += 4 * WSIZE;           // 指向序言块头部
    // 扩展堆到 CHUNKSIZE
    char* bp;
    if((bp = (char*)extend_heap(CHUNKSIZE / WSIZE)) == NULL) {
        return -1;
    }
    return 0;
}

/*
 * mm_malloc - 分配内存块。
 *
 * 功能：
 * - 查找适配的空闲块，分割并分配给用户。
 * - 如果没有适配块，则扩展堆。
 *
 * 实现：
 * 1. 对用户请求的大小进行对齐。
 * 2. 在空闲链表中查找适配块。
 * 3. 如果找到，分割块并分配。
 * 4. 如果未找到，扩展堆并分配新块。
 */

void *mm_malloc(size_t size)
{
    if(size == 0) return (void*)NULL;
    // 对请求大小进行对齐
    int asize = ALIGN(size + SIZE_T_SIZE);
    // 尝试找到合适的空闲块
    char *bp = find_fit(asize);
    if(bp != NULL) {
        place(bp, asize);
        return bp;
    }
    // 如果没有合适的空闲块，则扩展堆
    size_t extension_size = asize > CHUNKSIZE ? asize : CHUNKSIZE;
    if((bp = extend_heap(extension_size / WSIZE)) != NULL) {
        place(bp, asize);
        return bp;    
    }
    else {
        return (void*)NULL;
    }
}

/*
 * mm_free - 释放内存块。
 *
 * 功能：
 * - 将分配块标记为空闲，并尝试与相邻块合并。
 *
 * 实现：
 * 1. 更新块的分配标志。
 * 2. 调用 coalesce 合并相邻空闲块。
 */

void mm_free(void *ptr)
{
    size_t size = GET_SIZE(HDRP(ptr));
    // 将块头和块尾的分配标志设置为 0，表示释放
    PUT(HDRP(ptr), PACK(size, 0));
    PUT(FTRP(ptr), PACK(size, 0));
    // 尝试合并相邻的空闲块
    coalesce(ptr);
}

/*
 * mm_realloc - 调整分配块的大小。
 *
 * 功能：
 * - 分配新块，复制旧块数据，释放旧块。
 *
 * 实现：
 * 1. 如果新大小为0，相当于释放块。
 * 2. 如果旧指针为 NULL，相当于分配新块。
 * 3. 如果旧大小足够，不需要重新分配。
 * 4. 分配新块并复制数据，释放旧块。
 */

void *mm_realloc(void *ptr, size_t size)
{
    // 保存原指针，用于后续释放
    void *oldptr = ptr;
    void *newptr;
    size_t copySize;
    // 尝试为新内存块分配空间
    newptr = mm_malloc(size);
    if (newptr == NULL){
      return NULL;
    }
    if(oldptr == NULL) return newptr;
    // 确定需要复制的数据大小，取原块大小和新大小中的较小者
    copySize = GET_SIZE(HDRP(oldptr));
    if (size < copySize)
        copySize = size;
    // 将原内存块的数据拷贝到新内存块
    memcpy(newptr, oldptr, copySize);
    mm_free(oldptr);
    return newptr;
}